package com.algrithom.sort.insertsort;

import java.util.Arrays;

import com.util.CommonUtil;

/**
 * 直接插入排序
 *
 * @author think
 * @version 1.0.0
 * @since 2020/1/1
 */
class InsertSort {
    
    public static void main(String[] args){
        Integer[] array = new Integer[]{1,3,4,2,1,10,5};
        insertionSort(array);
        System.out.println(Arrays.toString(array));
    }
    
    /**
     * 插入排序
     *
     * @param array 数组
     */
    private static void insertionSort(Integer[] array){
        int len = array.length;
        int counter = 1;
        
        for (int i = 1; i < len; i++) {
            // 存储待排序的元素值
            int temp = array[i];
            // 与待排序元素值作比较的元素的下标
            int insertPoint = i - 1;
            // 当前元素比待排序元素大
            for (; insertPoint >= 0; insertPoint--) {
                if (array[insertPoint] > temp) {
                    // 当前元素后移一位
                    array[insertPoint + 1] = array[insertPoint];
                }
            }
            // 找到了插入位置，插入待排序元素
            array[insertPoint + 1] = temp;
            
            System.out.print("第" + counter + "轮排序结果：");
            CommonUtil.display(array);
            counter++;
        }
    }
    
    /**
     * 二分插入排序
     *
     * @param array 数组
     */
    void binaryInsertionSort(Integer[] array){
        
        int len = array.length;
        int counter = 1;
        
        for (int i = 1; i < len; i++) {
            // 存储待排序的元素值
            int temp = array[i];
            // 比有序数组的最后一个元素要小
            if (array[i - 1] > temp) {
                // 获取应插入位置的下标
                int insertIndex = binarySearch(array,i - 1,temp);
                // 将有序数组中，插入点之后的元素后移一位
                if (i - insertIndex >= 0) {
                    System.arraycopy(array,insertIndex,array,insertIndex + 1,i - insertIndex);
                }
                // 插入待排序元素到正确的位置
                array[insertIndex] = temp;
            }
            
            System.out.print("第" + counter + "轮排序结果：");
            CommonUtil.display(array);
            counter++;
        }
    }
    
    /**
     * 二分查找法 TODO 待完善
     *
     * @param array 数组
     * @param upperBound 查找段的最大下标
     * @param target 目标元素
     * @return 目标元素应该插入位置的下标
     */
    private int binarySearch(Integer[] array,int upperBound,int target){
        int curIndex;
        int lowerBound = 0;
        while (lowerBound < upperBound) {
            curIndex = (lowerBound + upperBound) / 2;
            if (array[curIndex] > target) {
                upperBound = curIndex - 1;
            } else {
                lowerBound = curIndex + 1;
            }
        }
        return lowerBound;
    }
    
    /**
     * 路插入排序 TODO 待完善
     */
    void two_wayInsertionSort(Integer[] array){
        int len = array.length;
        Integer[] newArray = new Integer[len];
        // 将原数组的第一个元素作为枢纽元素
        newArray[0] = array[0];
        // 指向最小元素的指针
        int first = 0;
        // 指向最大元素的指针
        int last = 0;
        // 打印初始化数组
        for (Integer item : newArray) {
            System.out.print(item + "\t");
        }
        System.out.println();
        
        for (int i = 1; i < len; i++) {
            // 大于等于最大元素，直接插入到last后面，不用移动元素
            if (array[i] >= newArray[last]) {
                last++;
                newArray[last] = array[i];
                // 小于最小元素，直接插到first前面，不用移动元素
            } else if (array[i] < newArray[first]) {
                first = (first - 1 + len) % len;
                newArray[first] = array[i];
                // 在最大值与最小值之间，且大于等于枢纽元素，插入到last之前，需要移动元素
            } else if (array[i] >= newArray[0]) {
                int curIndex = last;
                last++;
                do {
                    // 比array[i]大的元素后移一位
                    newArray[curIndex + 1] = newArray[curIndex];
                    curIndex--;
                } while (newArray[curIndex] > array[i]);
                // 插入到正确的位置
                newArray[curIndex + 1] = array[i];
            } else {
                // 在最大值与最小值之间，且小于枢纽元素，插入到first之后，需要移动元素
                int curIndex = first;
                first = (first - 1 + len) % len;
                do {
                    // 比array[i]小的元素前移一位
                    newArray[curIndex - 1] = newArray[curIndex];
                    curIndex = (curIndex + 1 + len) % len;
                } while (newArray[curIndex] <= array[i]);
                // 插入到正确的位置
                newArray[(curIndex - 1 + len) % len] = array[i];
            }
            // 打印新数组中的元素
            CommonUtil.display(newArray);
        }
    }
}
